
/**
 * 快速排序
 * 
 */
public class QuickSort {

    public int[] sortArray(int[] nums) {
        return quick_sort(nums, 0, nums.length - 1);
    }

    public int[] quick_sort(int[] nums, int left, int right) {
        if(left >= right) {
            return nums;
        }

        int pivotIndex = sort(nums, left, right);
        quick_sort(nums, left, pivotIndex - 1);
        quick_sort(nums, pivotIndex + 1, right);
        return nums;
    }

    public int sort(int[] nums, int left, int right) {
        int i = left;
        int j = right;
        int pivot = nums[left];

        while (i < j) {
            while(nums[i] < pivot && i < j) {
                i++;
            }
            while(nums[j] > pivot && j > i) {
                j--;
            }
            int temp = nums[i];

            nums[i] = nums[j];
            nums[j] = temp;
        }

        nums[i] = pivot;
        return i;
    }
}